package org.everyday;

import java.util.*;

/**
 * @version v1.0.0
 * 创建时间：2022/7/7 08:55
 */
public class L648 {
    public String replaceWords(List<String> dictionary, String sentence) {
        return replaceWordsWithTrie(dictionary,sentence);
    }

    private String replaceWordsWithSet(List<String> dictionary, String sentence){
        HashSet<String> set = new HashSet<>();
        dictionary.forEach(x -> set.add(x));
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                if (set.contains(word.substring(0, 1 + j))) {
                    words[i] = word.substring(0, 1 + j);
                    break;
                }
            }
        }
        return String.join(" ",words);
    }
    // 字典树或者前缀树 解法
    private String replaceWordsWithTrie(List<String> dictionary, String sentence){
        // 构建树
        Trie trie = new Trie();
        for (String word : dictionary) {
            Trie cur = trie;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                cur.children.putIfAbsent(c, new Trie());
                cur = cur.children.get(c);
            }
            cur.children.put('#', new Trie());
        }

        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            words[i] = findRoot(words[i], trie);
        }
        return  String.join(" ", words);
    }

    private String findRoot(String word,Trie trie){
        StringBuilder builder = new StringBuilder();
        Trie cur = trie;
        for (int i = 0; i < word.length(); i++) {
            if (cur.children.containsKey('#')){
                return builder.toString();
            }
            char c = word.charAt(i);
            if (!cur.children.containsKey(c)){
                return word;
            }
            builder.append(c);
            cur = cur.children.get(c);
        }
        // 前缀词和单词完全相同的情况
        return builder.toString();
    }

    class Trie {
        Map<Character, Trie> children;

        public Trie() {
            children = new HashMap<Character, Trie>();
        }
    }

    public static void main(String[] args) {
        new L648().replaceWordsWithTrie(Arrays.asList(new String[]{"a", "aa", "aaa", "aaaa"})
        ,"a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa");
    }
}
